package cn.com.colasoft.dataStructure;

/**
 * [高级排序之-希尔排序]
 * 复杂度:NlogN
 * 原理:
 * @author lizhitao
 * @date 2017/12/5
 */
public class ShellSort {

    public static void sort(long[] arrays) {
        int inner, outter;
        long temp;

        int h = 1;
        // 先计算出inner,outter比较时,两个索引下标的间隔.计算公式:h = (h*3) + 1
        // 计算出所有的间隔,但必须满足不大于(数组总元素/3)
        while (h <= arrays.length/3) { // 如果100个元素,则不能大于33
            h = (h*3) + 1;// 循环计算出所有间隔.如果有100个元素的话分别是:1 4 13 40
        }

        // 从间隔h最大的开始对两个元素进行比较,如果第一个位置的元素比第二个位置的元素大则交换值.
        // 随后,两个元素的位置继续向后移动,重复比较动作,直到outter达到末尾
        // 再后,对h所有剩余的间隔都将如此进行.此时计算h = (h-1)/3
        while (h > 0) {
            // 进行间隔排序
            for (outter = h; outter < arrays.length; outter++) {
                temp = arrays[outter];
                inner = outter;
                // 注意while判断时 inner >=h
                while (inner >= h && arrays[inner-h] >= temp) {
                    //arrays[outter] = arrays[outter-h];
                    //arrays[outter-h] = temp;
                    arrays[inner] = arrays[inner-h];
                    inner -= h;
                }
                arrays[inner] = temp;
            }

            h = (h-1)/3;
        }

    }

    public static void main(String[] args) {
        long[] arrays = new long[]{4,3,4,5,4,5,7,1};
        sort(arrays);

        for (long item : arrays) {
            System.out.print(item + ",");
        }
    }
}
